package leetcode.problems;

import org.junit.Test;

import java.util.*;

/**
 * Created by gmwang on 2018/7/25
 * 特别相同的字符串集合
 */
public class _0801GroupsOfSpecial_EquivalentStrings {
    /**
     *
     * You are given an array A of strings.
     * 给你一个字符串数组。
     *
     * Two strings S and T are special-equivalent if after any number of moves, S == T.
     * 两个字符串S和T是特殊等价的，如果在任何数量的移动之后，S＝T。
     *
     * A move consists of choosing two indices i and j with i % 2 == j % 2, and swapping S[i] with S[j].
     * 一个移动包括选择两个指数i和j，其中i %＝2＝J % 2，并用S [j]交换S[i]。
     *
     * Now, a group of special-equivalent strings from A is a non-empty subset S of A such that any string not in S is not special-equivalent with any string in S.
     * 现在，一组来自A的特殊等价字符串是A的非空子集S，使得任何不在S中的字符串都不与S中的任何字符串特别等价。
     *
     * Return the number of groups of special-equivalent strings from A.
     * 从A返回特殊等价字符串的组数。
     *
     * Example 1:
     *
     * Input: ["a","b","c","a","c","c"]
     * Output: 3
     * Explanation: 3 groups ["a","a"], ["b"], ["c","c","c"]
     * Example 2:
     *
     * Input: ["aa","bb","ab","ba"]
     * Output: 4
     * Explanation: 4 groups ["aa"], ["bb"], ["ab"], ["ba"]
     * Example 3:
     *
     * Input: ["abc","acb","bac","bca","cab","cba"]
     * Output: 3
     * Explanation: 3 groups ["abc","cba"], ["acb","bca"], ["bac","cab"]
     * Example 4:
     *
     * Input: ["abcd","cdab","adcb","cbad"]
     * Output: 1
     * Explanation: 1 group ["abcd","cdab","adcb","cbad"]
     *
     *
     * Note:
     *
     * 1 <= A.length <= 1000
     * 1 <= A[i].length <= 20
     * All A[i] have the same length.
     * All A[i] consist of only lowercase letters.
    /**
     * 获取每个句子中只出现过一次的词,再判断这个词在另一个句子中是否出现过
     * @param A,B
     * @return
     */
    public String[] uncommonFromSentences(String A, String B) {
        String[] As = A.split(" ");
        String[] Bs = B.split(" ");
        List<String> list = new ArrayList<>();
        Map<String, Integer> AMap = new HashMap<>();
        Map<String, Integer> BMap = new HashMap<>();
        for(int i=0;i< (As.length>=Bs.length?As.length:Bs.length);i++){
            if(i < As.length){
                //说明存在
                if(AMap.containsKey(As[i])) {
                    AMap.put(As[i],AMap.get(As[i]) + 1);
                }else{
                    AMap.put(As[i],1);
                }
            }
            if(i < Bs.length){
                //说明存在
                if(BMap.containsKey(Bs[i])) {
                    BMap.put(Bs[i],BMap.get(Bs[i]) + 1);
                }else{
                    BMap.put(Bs[i],1);
                }
            }
        }
        //取出只出现一次的，比较是否出现另一个map中
        for(int i=0;i< (As.length>=Bs.length?As.length:Bs.length);i++){
            if(i < As.length){
                //说明存在
                if(AMap.get(As[i]) != 1) {
                    //非 1 的什么也不干
                }else{
                    //不出现 则是不常见的
                    if(!BMap.containsKey(As[i])) list.add(As[i]);
                }
            }
            if(i < Bs.length){
                //说明存在
                if(BMap.get(Bs[i]) != 1) {
                    //非 1 的什么也不干
                }else{
                    //不出现 则是不常见的
                    if(!AMap.containsKey(Bs[i])) list.add(Bs[i]);
                }
            }
        }
        String[] array = new String[list.size()];
        for(int i = 0;i < list.size(); i ++){
            array[i] = list.get(i);
        }
        return array;
    }
    @Test
    public void test() {
        String sentence1 = "this apple is sweet";
        String sentence2 = "this apple is sour";
//        String sentence1 = "apple apple";
//        String sentence2 = "banana";
//        String sentence1 = "fd kss fd";
//        String sentence2 = "fd fd kss";
//        String sentence1 ="d b zu d t";
//        String sentence2 = "udb zu ap";
        String [] rs = uncommonFromSentences(sentence1,sentence2);
        System.out.println(Arrays.toString(rs));
    }
}
